//
//  47. 全排列问题II.swift
//  LeetCodeTrain
//
//  Created by rjb on 2021/6/29.
//  Copyright © 2021 rjb. All rights reserved.
//

import Foundation
class Solution47 {
    var result: [[Int]] = []
    var path: [Int] = []
    var used: [Bool] = []
    func permuteUnique(_ nums: [Int]) -> [[Int]] {
        let sortedNums = nums.sorted()
        used = Array(repeating: false, count: sortedNums.count)
        backTrace(sortedNums)
        return result
    }
    func backTrace(_ nums: [Int]) {
        if path.count == nums.count {
            result.append(path)
            return
        }
        for i in 0..<nums.count {
            let num = nums[i]
            // nums[i - 1] = num[i] 将横向与纵向都去重了
            // used[i - 1] == false 只是将横向去重
            if i > 0 && nums[i - 1] == num && used[i - 1] == false {
                continue
            }
            // 已经被访问过了的元素直接跳过
            // 此处也可以还剩下的数组用子数组表示
            if used[i] == true {
                continue
            }
            used[i] = true
            path.append(num)
            backTrace(nums)
            path.removeLast()
            used[i] = false
        }
    }
    
    // 第二种写法
//    func permuteUnique(_ nums: [Int]) -> [[Int]] {
//        let sortedNums = nums.sorted()
//        backTrace(sortedNums)
//        return result
//    }
//    func backTrace(_ nums: [Int]) {
//        if nums.count == 0 {
//            result.append(path)
//            return
//        }
//        for i in 0..<nums.count {
//            let num = nums[i]
//            if i > 0 && nums[i - 1] == num {
//                continue
//            }
//            var newNums = nums
//            newNums.remove(at: i)
//            path.append(num)
//            backTrace(newNums)
//            path.removeLast()
//        }
//    }
    static func test(){
        let solution = Solution47()
        let nums = [1,1,2]
        let result = solution.permuteUnique(nums)
        print(result)
    }
}
